Value function approximation has demonstrated phenomenal empirical success in reinforcement learning (RL). Nevertheless, despite a handful of recent progress on developing theory for RL with linear function approximation, the understanding of \emph{general} function approximation schemes largely remains missing. In this paper, we establish the first provably efficient RL algorithm with general value function approximation. We show that if the value functions admit an approximation with a function class $\mathcal{F}$, our algorithm achieves a regret bound of $\widetilde{O}(\mathrm{poly}(dH)\sqrt{T})$ where $d$ is a complexity measure of $\mathcal{F}$ that depends on the eluder dimension~[Russo and Van Roy, 2013] and log-covering numbers, $H$ is the planning horizon, and $T$ is the number interactions with the environment.

Value function approximation has demonstrated phenomenal empirical success in reinforcement learning (RL). Nevertheless, despite a handful of recent progress on developing theory for RL with linear function approximation, the understanding of \emph{general} function approximation schemes largely remains missing. In this paper, we establish the first provably efficient RL algorithm with general value function approximation. We show that if the value functions admit an approximation with a function class \mathcal{F}, our algorithm achieves a regret bound of \widetilde{O}(\mathrm{poly}(dH)\sqrt{T}) where d is a complexity measure of \mathcal{F} that depends on the eluder dimension [Russo and Van Roy, 2013] and log-covering numbers, H is the planning horizon, and T is the number interactions with the environment. Moreover, our algorithm is model-free and provides a framework to justify the effectiveness of algorithms used in practice.

This assumption is crucial for dynamic programming type of analysis. Although it seems to be just an assumption on the value function class, it actually also implicit makes assumption about the MDP. The difference between the sensitive sampling in this paper and the prior work also need to be discussed more. Moreover, the connection between Lemma 9 and 10 and Proposition 3 and Lemma 2 in [44] also need to be discussed. I think these discussions will be helpful for people to understand the details and digest the proof.

The problem of exploration in RL with function approximation is very important and any advancement on the topic is of interest for the community. The reviewers all agreed about the algorithmic and technical contribution of the paper, in particular the introduction of sensitive sampling and its analysis in the regret proof. This convinced us that the paper deserves acceptance. Nonetheless, I also encourage the authors to improve the current submission. As pointed out by R3, the assumptions used in the paper are quite strong and they may somehow limit the generality of the results.

Value function approximation has demonstrated phenomenal empirical success in reinforcement learning (RL). Nevertheless, despite a handful of recent progress on developing theory for RL with linear function approximation, the understanding of \emph{general} function approximation schemes largely remains missing. In this paper, we establish the first provably efficient RL algorithm with general value function approximation. We show that if the value functions admit an approximation with a function class \mathcal{F}, our algorithm achieves a regret bound of \widetilde{O}(\mathrm{poly}(dH)\sqrt{T}) where d is a complexity measure of \mathcal{F} that depends on the eluder dimension [Russo and Van Roy, 2013] and log-covering numbers, H is the planning horizon, and T is the number interactions with the environment. Moreover, our algorithm is model-free and provides a framework to justify the effectiveness of algorithms used in practice.